#include"Graph.h"
#include"MakeGraph.h"
template<class solving_problem> 
void DepthFirstSearch(Graph &graph, solving_problem &Task){
    int graph_size = graph.GetNumberOfVertices();
    std::stack< int > processing_vertices;
    std::vector <bool> used(graph_size, false); 
    for(int vertex = 0; vertex < graph_size; vertex++){
        if(!used[vertex]){
            used[vertex] = true;
            Task.EnterVertex(vertex);
            processing_vertices.push(vertex);
            while(!processing_vertices.empty()){
                int current_vertex = processing_vertices.top();
                bool vertex_added_to_stack = false;
                std::set <int> incident_vertices = graph.GetIncidentList(current_vertex);
                for(std::set<int>::iterator tmp_ver = incident_vertices.begin(); tmp_ver != incident_vertices.end(); tmp_ver++){
                    Task.ProcessEdge(current_vertex, *tmp_ver);
                    if(!used[*tmp_ver] ){
                        used[*tmp_ver] = true;
                        Task.EnterVertex(*tmp_ver);
                        processing_vertices.push(*tmp_ver);
                        vertex_added_to_stack = true;
                    }
                 }
                if(!vertex_added_to_stack){
                    processing_vertices.pop();
                    Task.LeaveVertex(current_vertex);   
                }
            }
        }
    }
}

enum DFSStage{
    NOT_VISITED,
    PROCESSING,
    LEFT
};


class TopologicalSort{
public:
    TopologicalSort(int vertices_number) : state(vertices_number, NOT_VISITED) {}
    void EnterVertex(int vertex){
        state[vertex] = PROCESSING;
    }
    void ProcessEdge(int begin_vertex, int end_vertex){
        try{
            if(state[end_vertex] == PROCESSING){
                throw std::logic_error("ERROR: Circle found in given Graph");
            }
        } catch (const std::exception& ex){
            throw std::logic_error(std::string(ex.what()));
        };
    }
    void LeaveVertex(int vertex){
        if(state[vertex] == PROCESSING){
            SortedGraph.push_back(vertex);
            state[vertex] = LEFT;
        }
        
    }
    std::vector<int> GetSortedGraph(){
        std::vector <int> answer = SortedGraph;
	std::reverse(answer.begin(), answer.end());
	return answer;
    }
private:
    std::vector<int> SortedGraph;
    std::vector<DFSStage> state;
};

template<class solving_problem>
void BreadthFirstSearch(Graph &graph, solving_problem &Task){
    int vertices_number = graph.GetNumberOfVertices();
    std::queue<int> processing_vertices;
    std::vector<bool> used(vertices_number, false);
    for(int vertex = 0; vertex < vertices_number; vertex++){
        if(!used[vertex]){
            used[vertex] = true;
            Task.EnterVertex(vertex);
            processing_vertices.push(vertex);
            while(!processing_vertices.empty()){
                int current_vertex = processing_vertices.front();
                processing_vertices.pop();
                std::set <int> incident_vertices = graph.GetIncidentList(current_vertex);
                for(std::set<int>::iterator tmp_ver = incident_vertices.begin(); tmp_ver != incident_vertices.end(); tmp_ver++){
                    Task.ProcessEdge(current_vertex, *tmp_ver);
                    if(!used[*tmp_ver] ){
                        used[*tmp_ver] = true;
                        Task.EnterVertex(*tmp_ver);
                        processing_vertices.push(*tmp_ver);
                    }
                }
            }
        }
    }
}